package gold.digger;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC52 {
    public long startExecuteTime = System.currentTimeMillis();


    class Solution {
        int count = 0;

        public int totalNQueens(int n) {
            char[][] board = new char[n][n];
            travelNQueensRecur(board, 0);
            return count;
        }

        public void travelNQueensRecur(char[][] board, int curLine) {
            if (curLine == board.length) {
                ++count;
                return;
            }

            for (int i = 0; i < board[curLine].length; i++) {
                board[curLine][i] = 'Q';
                if (validate(board, curLine, i)) {
                    travelNQueensRecur(board, curLine + 1);
                }
                board[curLine][i] = 0;
            }
        }

        private boolean validate(char[][] board, int x, int y) {
            for (int i = x - 1; i >= 0; i--) {
                if (board[i][y] == 'Q') return false;
                if (y - (x - i) >= 0 && board[i][y - (x - i)] == 'Q') return false;
                if (y + (x - i) < board.length && board[i][y + (x - i)] == 'Q') return false;
            }

            return true;
        }
    }

    public void run() {
        Solution solution = new Solution();
        System.out.println(solution.totalNQueens(4));
    }

    public static void main(String[] args) throws Exception {
        LC52 an = new LC52();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
